package com.company.algo.complicateStruct.cacheStruct.lru;

import java.util.HashMap;

class Node {
    public int key, value;
    public Node pre, next;
    public Node(int k, int v){
        this.key = k;
        this.value = v;
    }
}
class DoubleList{
    private Node head, tail;
    private int size;
    public DoubleList(){
        head = new Node(0,0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }
    // 在链表尾部添加节点 x，时间 O(1)
    public void addLast(Node x){
        x.pre = tail.pre;
        x.next = tail;
        tail.pre.next = x;
        tail.pre = x;
        size ++;
    }
    // 删除链表中的 x 节点（x 一定存在）时间 O(1)
    public void remove(Node x){
        x.pre.next = x.next;
        x.next.pre = x.pre;
        size --;
    }
    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public Node removeFirst(){
        if (head.next == tail) return null;
        Node first = head.next;
        remove(first);
        return first;
    }
    // 返回链表长度，时间 O(1)
    public int size(){return size;}
}

class MyLRUCache {
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;

    public MyLRUCache(int capability){
        this.cap = capability;
        this.map = new HashMap<>();
        this.cache = new DoubleList();
    }

    //cache的尾节点为最近使用的
    public void makeRecently(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    //添加节点，同时往map和cache中添加
    public void addRecently(int k, int v){
        Node x = new Node(k,v);
        map.put(k,x);
        cache.addLast(x);
    }

    //删除节点的时候需要同时操作cache和map
    public void deleteByKey(int key){
        Node x = map.get(key);
        map.remove(key);
        cache.remove(x);
    }

    //删除最少使用的节点
    public void removeLeastUsed(){
        Node x = cache.removeFirst();
        map.remove(x.key);
    }

    //get需要判断是否存在
    public int get(int k){
        if (!map.containsKey(k)) return -1;
        makeRecently(k);
        return map.get(k).value;
    }

    //put需要考虑两种情况
    public void put(int k, int v){
        //已有的数据将之变为最新
        if (map.containsKey(k)){
            //删除旧的数据，并插入新的数据
            deleteByKey(k);
            addRecently(k,v);
            return;
        }
        //没有的数据需要添加，添加前判别是否缓存已满
        if (cap == cache.size()){
            removeLeastUsed();
        }
        addRecently(k,v);
    }


}